OGR's
"In mathematics, the term "Golomb Ruler" refers to a set of non-negative integers such that no two distinct pairs of numbers from the set have the same difference. Conceptually, this is similar to a ruler constructed in such a way that no two pairs of marks measure the same distance. An Optimal Golomb Ruler (OGR) is the shortest Golomb Ruler possible for a given number of marks.
Golomb rulers are named after Dr. Solomon W. Golomb, a professor of Mathematics with a special interest in combinatorial analysis, number theory, coding theory and communications. OGR's have many applications including sensor placements for X-ray crystallography and radio astronomy. Golomb rulers can also play a significant role in combinatorics, coding theory and communications, and Dr. Golomb was one of the first to analyze them for use in these areas.
A Golomb ruler is a way to place marks along a line such that each pair of marks measures a unique linear distance. Here is a Golomb ruler with five marks:
| | | | |
0 1 4 9 11
The number below the mark is the distance from the left edge. The length of this ruler is 11, and it happens to be one of the two shortest such rulers with five marks. The other ruler has marks at positions 0, 3, 4, 9, and 11. (The mirror images of these two rulers, 0, 2, 7, 10, 11 and 0, 2, 7, 8, 11, are also optimal Golomb rulers. Usually just one of each mirror-image pair is mentioned.)"
Unfortunately, the search for OGRs becomes exponentially more difficult as the number of marks increases (similar to what mathematicians call "Np complete" problems ... like the infamous Traveling Salesman optimization ;-)).
Anyway, that, in a nut shell, is a Golomb Ruler! If you want a more complete description please do little googling!
Excogitated by a_beautifulmind @ 3:00 PM
0 Voiced their opinions :
Post a Comment
<< Home